package com.xiyou.week01.stack;

import java.util.Stack;

/**
 * 224. 基本计算器
 *
 * @ClassName：LeetCode225
 * @Author：西柚
 * @Date：2021/11/22 3:00 下午
 * @Versiion：1.0
 */
public class Calculate {

    /**
     * 输入：s = "(1+(4+5+2)-3)+(6+8)"
     * 输出：23
     *
     * @param s
     * @return
     */
    public int calculate(String s) {
        s += " ";
        Stack<String> tokens = new Stack<String>();
        Stack<String> ops = new Stack<String>();
        String number = "";
        Boolean needsZero = true;
        for (char c : s.toCharArray()) {
            if (c < '0') {//加减乘除和空格ASCII码都小于'0'
                if (!"".equals(number)) {
                    tokens.push(number);
                    number = "";
                }

                if (c == ' ') {
                    continue;
                }
            } else {
                number += c;
                needsZero = false;
                continue;
            }

            if (c == '(') {
                ops.push(String.valueOf(c));
                needsZero = true;
                continue;
            } else if (c == ')') {
                while (!"(".equals(ops.peek())) {
                    tokens.push(ops.pop());
                    continue;
                }
                ops.pop();
                needsZero = false;
                continue;
            }

            if ((c == '+' || c == '-') && needsZero) {
                tokens.push(String.valueOf(0));
            }

            int currRank = getRank(String.valueOf(c));
            while (!ops.isEmpty() && getRank(ops.peek()) >= currRank) {
                tokens.push(ops.pop());
            }
            ops.push(String.valueOf(c));
            needsZero = true;
        }

        while (!ops.isEmpty()) {
            tokens.push(ops.pop());
        }
        return evalRPN(tokens);
    }

    private int getRank(String s) {
        if ("*".equals(s) || "/".equals(s)) {
            return 2;
        } else if ("+".equals(s) || "-".equals(s)) {
            return 1;
        }
        return 0;
    }

    public int evalRPN(Stack<String> tokens) {
        Stack<Integer> stack = new Stack<Integer>();
        for (String token : tokens) {
            if ("+".equals(token)) {
                Integer y = stack.pop();
                stack.push(stack.pop() + y);
            } else if ("-".equals(token)) {
                Integer y = stack.pop();
                stack.push(stack.pop() - y);
            } else if ("*".equals(token)) {
                Integer y = stack.pop();
                stack.push(stack.pop() * y);
            } else if ("/".equals(token)) {
                Integer y = stack.pop();
                stack.push(stack.pop() / y);
            } else {
                stack.push(Integer.valueOf(token));
            }
        }
        return stack.pop();
    }

    public static void main(String[] args) {
        Calculate leetCode224 = new Calculate();

        String s = "(1+(4+5+2)-3)+(6+8)";
//        String s = "-2+1";
        System.out.println(leetCode224.calculate(s));
    }
}
